0316. 去除重复字母【中等】

• 1. 📝 题目描述
• 2. 🎯 s.1 - 单调栈 + 贪心
• 3. 🔗 引用

1. 📝 题目描述

• leetcode

给你一个字符串 s，请你去除字符串中重复的字母，使得每个字母只出现一次。需保证 返回结果的字典序最小（要求不能打乱其他字符的相对位置）。

字典序更小

考虑字符串 a 与 字符串 b，如果字符串 a 在 a 与 b 相异的第一处的字符在字母表上先于对应 b 在此处的字符出现，则称字符串 a 字典序小于 b。如果 a 或 b 其中较短的字符串为另一个字符串的前半部分，则较短的字符串字典序小于另一个字符串。

---

示例 1：

输入：s = "bcabc"
输出："abc"

示例 2：

输入：s = "cbacdcbc"
输出："acdb"

---

提示：

• 1 <= s.length <= 10^4
• s 由小写英文字母组成

---

注意：该题与 1081. 不同字符的最小子序列 相同

2. 🎯 s.1 - 单调栈 + 贪心

c

char* removeDuplicateLetters(char* s) {
    int lastIndex[26] = {0};
    int len = strlen(s);
    for (int i = 0; i < len; i++) lastIndex[s[i] - 'a'] = i;
    char* stack = (char*)malloc(27);
    bool inStack[26] = {false};
    int top = 0;
    for (int i = 0; i < len; i++) {
        int c = s[i] - 'a';
        if (inStack[c]) continue;
        while (top > 0 && stack[top - 1] > s[i] && lastIndex[stack[top - 1] - 'a'] > i) {
            inStack[stack[--top] - 'a'] = false;
        }
        stack[top++] = s[i];
        inStack[c] = true;
    }
    stack[top] = '\0';
    return stack;
}

js

/**
 * @param {string} s
 * @return {string}
 */
var removeDuplicateLetters = function (s) {
  const lastIndex = new Array(26).fill(-1)
  for (let i = 0; i < s.length; i++) lastIndex[s.charCodeAt(i) - 97] = i
  const stack = []
  const inStack = new Array(26).fill(false)
  for (let i = 0; i < s.length; i++) {
    const c = s.charCodeAt(i) - 97
    if (inStack[c]) continue
    while (
      stack.length &&
      stack[stack.length - 1] > c &&
      lastIndex[stack[stack.length - 1]] > i
    ) {
      inStack[stack.pop()] = false
    }
    stack.push(c)
    inStack[c] = true
  }
  return stack.map((c) => String.fromCharCode(c + 97)).join('')
}

py

class Solution:
    def removeDuplicateLetters(self, s: str) -> str:
        last_index = {c: i for i, c in enumerate(s)}
        stack = []
        in_stack = set()
        for i, c in enumerate(s):
            if c in in_stack:
                continue
            while stack and stack[-1] > c and last_index[stack[-1]] > i:
                in_stack.discard(stack.pop())
            stack.append(c)
            in_stack.add(c)
        return ''.join(stack)

• 时间复杂度：$O(n)$，其中 $n$ 是字符串长度
• 空间复杂度：$O(|\mathrm{\Sigma }|)$，栈最多存储 26 个字符

算法思路：

• 维护单调递增栈，确保字典序最小
• 当栈顶字符大于当前字符且后面还会出现时，弹出栈顶
• 用 inStack 标记避免重复入栈

3. 🔗 引用

• 1081. 不同字符的最小子序列